// fastvec.h - Copyright (C) 2013 Willow Schlanger. All rights reserved. See univm_license.txt.
// --------------------------------------------------------------------------------------------
//    This header file is not automatically included. It implements infrared_sysbase::fastvec_t
// which is a container class similar to std::vector. You should include <infrared/infrared.h>
// first and then include this file; if that is done, fastvec_t can be accessed via simply
// isb::fastvec_t.
//    Like std::vector, fastvec_t is an array-like container that can be resized without moving
// data. Its main benefit over a vector is that even if you have a very large data set, your
// program will never need to pause so the vector can be resized. It also fragments memory
// less since growing it never requires deallocation. Although std::vector's have good
// amortized complexity, for e.g. an interactive environment one sometimes doesn't want to have
// to wait for all those old data items to be moved.
//    The price to pay for this is that adding/subtracting an iterator is slightly slower and
// requires something like log(log(N)) operations. [This is no big deal: the worst case should
// be 5-6 ops on a 32-bit or 64-bit platform].
//    Actually, we do lazy seeks, so it's even faster: you can seek all you want and this 5-6
// "op" penalty happens only the first time you dereference a fastvec_t iterator after having
// done a seek that takes us outside the current segment. So this is sort of a non-issue.
//    fastvec_t<> works by allocating up to 32 or 64 references. The 1st reference receives an
// array of 16 objects as soon as the first object is inserted. Then, when you try to insert
// an object that would bring the total above 16, a second segment (using the second array
// reference, out of 32 or 64 maximum) is allocated. The second segment then is an array of
// 32 objects (twice the size of the 1st segment).
//    Unlike a vector, we don't move data items from the first to the second; the first
// segment contains items 0..15 inclusive whereas the second, contains data items 16..47
// inclusve; the third: 48..111, etc. So each segment is twice as large as the previous, but
// items in a segment start where the previous segment left off.
//    Whole segments are allocated / deallocated at a time, with constructors / destructors
// being called correctly. There is some overhead; on a 32-bit platform, an empty
// fastvec_t<int> requires 28 bytes of memory. Also note that we align elements on a 64-bit
// boundary and at any one time we could have "preallocated" memory for more objects than are
// actually in use in the container.
//    If you have 17 objects in the container, we've got space for 48 objects. If you've got
// 49 objects, we've got space for 112. If you've got 113, you've got space for 240. So we
// quickly approach a situation where at most half the memory is reserved but not in use.
// --------------------------------------------------------------------------------------------
// Sample code:
//    #include <infrared/infrared.h>
//    #include <infrared/fastvec.h>
//    .
//    .
//    .
//    isb::fastvec_t<int> myvec;
//    myvec.push_back(123);
//    int x = myvec[0];
//    myvec[0] = 456;
//    int y = myvec[0] - x;			// should be 333
//
// Note: We also support iterators and the most commonly used operations std::vector supports.
// --------------------------------------------------------------------------------------------
// This container class can operate in a multithreaded environment, but you don't want several
// threads accessing the same fastvec_t container simultaneously unless only read operations
// are being performed.
//    Unlike std::vector<>, one can add/remove items from a fastvec_t without invalidating
// iterators. If you do a push_back() or resize() in a way that grows the container, then an
// iterator that was previously at the end might no longer be at the end. If you resize() in a
// way that shrinks the container, or pop_back() or clear(), then any iterators refering to a
// position that comes at or after the new size are now invalid (because you removed elements).
// ============================================================================================

#ifndef l_fastvec_h__infrared_isb__included
#define l_fastvec_h__infrared_isb__included

#include <infrared/sysbase.h>

namespace infrared_sysbase
{
namespace fastvec_internal
{
using namespace infrared_sysbase;

template <class ValueType>
class raw_value_t
{
public:
	U8 data[(sizeof(ValueType) + sizeof(U8) - 1) / sizeof(U8)];
};

template <class ValueType>
class level_ref_t
{
public:
	enum
	{
		MAX_NUM_LEVELS = 8 * sizeof(void *)
	};

	typedef ref_t<raw_value_t<ValueType> > level_type;

private:
	ref_t<level_type> *levels;
	
	level_ref_t() { }	// not allowed

public:
	void clear()
	{
		levels->clear();
	}

	explicit level_ref_t(ref_t<level_type> *p_levels) :
		levels(p_levels)
	{
	}
	
	level_ref_t(const level_ref_t &src) :
		levels(src.levels)
	{
	}
	
	level_ref_t &operator=(const level_ref_t &src)
	{
		levels = src.levels;
		return *this;
	}

	void set(usize_t n, level_type src)
	{
		if(!levels->is_null() && n < levels->size())
		{
			(*levels)[n] = src;
			return;
		}
	
		if(n >= MAX_NUM_LEVELS)
			return;		// error
		
		usize_t m = 1;
		while(m <= n)
			m += m;		// compute powers of 2 until m > n

		if(m >= MAX_NUM_LEVELS)
		{
			m = MAX_NUM_LEVELS;
			if(n >= m)
				return;		// error
		}
		
		ref_t<level_type> tmp = ref_t<level_type>::allocate_array(m);
		if(!levels->is_null())
		{
			for(usize_t i = 0; i < levels->size(); ++i)
				tmp[i] = (*levels)[i];
		}
		
		*levels = tmp;
		(*levels)[n] = src;
	}
	
	level_type &operator[](usize_t n)
	{
		if(levels->is_null() || n >= levels->size())
			return null_ref;		// return a null reference
		return (*levels)[n];
	}

private:
	level_type null_ref;
};

struct fastvec_base_t
{
	static U8 shl64(U8 src, U1 count)
	{
		count &= 63;

		// Some 64-bit compilers mask their shift count to 5 bits instead of 6.
		if(count >= 32)
		{
			src <<= 16;
			src <<= 16;
			count -= 32;
		}

		src <<= count;

		return src;
	}

	static usize_t get_level_size(usize_t level_num)
	{
		return shl64(16, level_num);
	}

	static usize_t pos_from_level(usize_t level)
	{
		// index 0..15 <-> level 0    0..f
		// index 16..47 <-> level 1   10..2f
		// index 48..111 <-> level 2  30..6f
		usize_t n = shl64(1, level) - 1;
		return n << 4;
	}

	static usize_t level_from_pos(usize_t index)
	{
		usize_t lmin = 0, lmax = 8 * sizeof(void *) - 1;
		usize_t lmid = 0;
		
		while(lmax >= lmin)
		{
			lmid = (lmin + lmax) / 2;	// no risk of overflow here
			usize_t mid_begin = pos_from_level(lmid);
			usize_t mid_end = pos_from_level(lmid + 1) - 1;
			
			if(index > mid_end)
				lmin = lmid + 1;
			else
			if(index < mid_begin)
				lmax = lmid - 1;
			else
				break;
		}
		
		return lmid;
	}
};

// Note that iterators do not hold a reference to their container, so you want to keep the
// container (or a reference to it) in scope wherever an iterator refering to it could be active.
template <class ValueType, class CValueType>
class fastvec_iterator_base_t
{
	level_ref_t<ValueType> p_levels;
	const usize_t *p_actual_size;
	CValueType *p_value;							// valid only if level != 65536
	usize_t position;
	usize_t level;									// level 65536 means 'invalidated'

public:
	fastvec_iterator_base_t(const fastvec_iterator_base_t &src) :
		p_levels(src.p_levels),
		p_actual_size(src.p_actual_size),
		p_value(src.p_value),
		position(src.position),
		level(src.level)
	{
	}
	
	// Create a new end() iterator.
	fastvec_iterator_base_t(level_ref_t<ValueType> p_levelsT, const usize_t *p_actual_sizeT) :
		p_levels(p_levelsT)
	{
		p_actual_size = p_actual_sizeT;
		p_value = NULL;
		position = *p_actual_size;
		level = 65536;								// mark invalidated
	}
	
	// Create a new iterator at the indicated position.
	fastvec_iterator_base_t(level_ref_t<ValueType> p_levelsT, const usize_t *p_actual_sizeT, usize_t positionT) :
		p_levels(p_levelsT)
	{
		p_actual_size = p_actual_sizeT;
		p_value = NULL;
		position = positionT;
		level = 65536;								// mark invalidated
	}

protected:
	usize_t get_pos() const
	{
		return position;
	}
	
	// This uniquely identifies the container.
	const usize_t *get_actual_size_ptr() const
	{
		return p_actual_size;
	}

	CValueType *get_ptr()
	{
		do_validate();
		return p_value;
	}

	void do_skip(usize_t count)
	{
		if(count == 0)
			return;

		position += count;
		
		if(position >= *p_actual_size)
			position = *p_actual_size;
		else
		if(level != 65536)
		{
			if(position < fastvec_base_t::pos_from_level(level + 1))
			{
				//p_value += count;
				const usize_t object_size_qwords = (sizeof(ValueType) + sizeof(U8) - 1) / sizeof(U8);
				p_value = (CValueType *)((U8 *)(p_value) + object_size_qwords * count);
				return;
			}
		}

		level = 65536;							// mark invalidated
		p_value = NULL;
	}
	
	void do_validate()
	{
		if(level == 65536 && position < *p_actual_size)
		{
			const usize_t object_size_qwords = (sizeof(ValueType) + sizeof(U8) - 1) / sizeof(U8);
			level = fastvec_base_t::level_from_pos(position);
			usize_t offset = position - fastvec_base_t::pos_from_level(level);
			U8 *level_data = p_levels[level]->data;
			p_value = (CValueType *)(level_data + object_size_qwords * offset);
		}
	}
	
	void do_rewind(usize_t count)
	{
		if(count == 0)
			return;
		if(count > position)
			count = position;
		
		position -= count;

		if(level == 0)
		{
			//p_value -= count;
			const usize_t object_size_qwords = (sizeof(ValueType) + sizeof(U8) - 1) / sizeof(U8);
			p_value = (CValueType *)((U8 *)(p_value) - object_size_qwords * count);
			return;
		}

		if(level != 65536)
		{
			if(position >= fastvec_base_t::pos_from_level(level))
			{
				//p_value -= count;
				const usize_t object_size_qwords = (sizeof(ValueType) + sizeof(U8) - 1) / sizeof(U8);
				p_value = (CValueType *)((U8 *)(p_value) - object_size_qwords * count);
				return;
			}
		}
		
		do_invalidate();						// mark invalidated
	}

	void do_invalidate()
	{
		level = 65536;
		p_value = NULL;
	}
};

template <class ValueType>
class fastvec_iterator_t :
	public fastvec_iterator_base_t<ValueType, ValueType>
{
	usize_t do_get_pos() const
	{
		return fastvec_iterator_base_t<ValueType, ValueType>::get_pos();
	}
	
	void *do_get_container() const
	{
		return (void *)(fastvec_iterator_base_t<ValueType, ValueType>::get_actual_size_ptr());
	}

public:
	fastvec_iterator_t(const fastvec_iterator_t &src) :
		fastvec_iterator_base_t<ValueType, ValueType>(*((const fastvec_iterator_base_t<ValueType, ValueType> *)(&src)))
	{
	}

	// Create an end iterator.
	template <class T1>
	fastvec_iterator_t(T1 p_levelsT, usize_t *p_actual_sizeT) :
		fastvec_iterator_base_t<ValueType, ValueType>(p_levelsT, p_actual_sizeT)
	{
	}
	
	// Create an iterator at the indicated position.
	template <class T1>
	fastvec_iterator_t(T1 p_levelsT, usize_t *p_actual_sizeT, usize_t posT) :
		fastvec_iterator_base_t<ValueType, ValueType>(p_levelsT, p_actual_sizeT, posT)
	{
	}
	
	ValueType &operator*()
	{
		return *(fastvec_iterator_base_t<ValueType, ValueType>::get_ptr());
	}
	
	ValueType *operator->()
	{
		return fastvec_iterator_base_t<ValueType, ValueType>::get_ptr();
	}
	
	fastvec_iterator_t &operator++()  /* prefix increment */
	{
		fastvec_iterator_base_t<ValueType, ValueType>::do_skip(1);
		return *this;
	}
	
	fastvec_iterator_t &operator--()  /* prefix decrement */
	{
		fastvec_iterator_base_t<ValueType, ValueType>::do_rewind(1);
		return *this;
	}
	
	fastvec_iterator_t &operator+=(usize_t count)
	{
		fastvec_iterator_base_t<ValueType, ValueType>::do_skip(count);
		return *this;
	}
	
	fastvec_iterator_t &operator-=(usize_t count)
	{
		fastvec_iterator_base_t<ValueType, ValueType>::do_rewind(count);
		return *this;
	}
	
	fastvec_iterator_t operator++(int)  /* postfix increment */
	{
		fastvec_iterator_t tmp = *this;
		++*this;
		return tmp;
	}
	
	fastvec_iterator_t operator--(int)  /* postfix decrement */
	{
		fastvec_iterator_t tmp = *this;
		--*this;
		return tmp;
	}
	
	fastvec_iterator_t operator+(usize_t count) const
	{
		fastvec_iterator_t tmp = *this;
		tmp += count;
		return tmp;
	}
	
	fastvec_iterator_t operator-(usize_t count) const
	{
		fastvec_iterator_t tmp = *this;
		tmp -= count;
		return tmp;
	}
	
	sptrdiff_t operator-(const fastvec_iterator_t &src) const
	{
		sptrdiff_t a = this->do_get_pos();
		sptrdiff_t b = src.do_get_pos();
		return a - b;
	}
	
	bool operator==(const fastvec_iterator_t &src) const
	{
		return src.do_get_container() == this->do_get_container() && src.do_get_pos() == this->do_get_pos();
	}
	
	bool operator!=(const fastvec_iterator_t &src) const
	{
		return src.do_get_pos() != this->do_get_pos() || src.do_get_container() != this->do_get_container();
	}
	
	bool operator<(const fastvec_iterator_t &src) const
	{
		if(src.do_get_container() == this->do_get_container())
		{
			return this->do_get_pos() < src.do_get_pos();
		}
		return this->do_get_container() < src.do_get_container();
	}

	ValueType &operator[](usize_t n)
	{
		if(n == 0)
			return **this;
		fastvec_iterator_t tmp = *this;
		tmp += n;
		return *tmp;
	}
};

template <class ValueType>
class fastvec_const_iterator_t :
	public fastvec_iterator_base_t<ValueType, const ValueType>
{
	usize_t do_get_pos() const
	{
		return fastvec_iterator_base_t<ValueType, const ValueType>::get_pos();
	}
	
	void *do_get_container() const
	{
		return (void *)(fastvec_iterator_base_t<ValueType, const ValueType>::get_actual_size_ptr());
	}

public:
	fastvec_const_iterator_t(const fastvec_const_iterator_t &src) :
		fastvec_iterator_base_t<ValueType, const ValueType>(*((const fastvec_iterator_base_t<ValueType, const ValueType> *)(&src)))
	{
	}

	// Create an end iterator.
	template <class T1>
	fastvec_const_iterator_t(T1 p_levelsT, const usize_t *p_actual_sizeT) :
		fastvec_iterator_base_t<ValueType, const ValueType>(p_levelsT, p_actual_sizeT)
	{
	}
	
	// Create an iterator at the indicated position.
	template <class T1>
	fastvec_const_iterator_t(T1 p_levelsT, const usize_t *p_actual_sizeT, usize_t posT) :
		fastvec_iterator_base_t<ValueType, const ValueType>(p_levelsT, p_actual_sizeT, posT)
	{
	}
	
	const ValueType &operator*()
	{
		return *(fastvec_iterator_base_t<ValueType, const ValueType>::get_ptr());
	}
	
	const ValueType *operator->()
	{
		return fastvec_iterator_base_t<ValueType, const ValueType>::get_ptr();
	}
	
	fastvec_const_iterator_t &operator++()  /* prefix increment */
	{
		fastvec_iterator_base_t<ValueType, const ValueType>::do_skip(1);
		return *this;
	}
	
	fastvec_const_iterator_t &operator--()  /* prefix decrement */
	{
		fastvec_iterator_base_t<ValueType, const ValueType>::do_rewind(1);
		return *this;
	}
	
	fastvec_const_iterator_t &operator+=(usize_t count)
	{
		fastvec_iterator_base_t<ValueType, const ValueType>::do_skip(count);
		return *this;
	}
	
	fastvec_const_iterator_t &operator-=(usize_t count)
	{
		fastvec_iterator_base_t<ValueType, const ValueType>::do_rewind(count);
		return *this;
	}
	
	fastvec_const_iterator_t operator++(int)  /* postfix increment */
	{
		fastvec_const_iterator_t tmp = *this;
		++*this;
		return tmp;
	}
	
	fastvec_const_iterator_t operator--(int)  /* postfix decrement */
	{
		fastvec_const_iterator_t tmp = *this;
		--*this;
		return tmp;
	}
	
	fastvec_const_iterator_t operator+(usize_t count) const
	{
		fastvec_const_iterator_t tmp = *this;
		tmp += count;
		return tmp;
	}
	
	fastvec_const_iterator_t operator-(usize_t count) const
	{
		fastvec_const_iterator_t tmp = *this;
		tmp -= count;
		return tmp;
	}
	
	sptrdiff_t operator-(const fastvec_const_iterator_t &src) const
	{
		sptrdiff_t a = this->do_get_pos();
		sptrdiff_t b = src.do_get_pos();
		return a - b;
	}
	
	bool operator==(const fastvec_const_iterator_t &src) const
	{
		return src.do_get_container() == this->do_get_container() && src.do_get_pos() == this->do_get_pos();
	}
	
	bool operator!=(const fastvec_const_iterator_t &src) const
	{
		return src.do_get_pos() != this->do_get_pos() || src.do_get_container() != this->do_get_container();
	}
	
	bool operator<(const fastvec_const_iterator_t &src) const
	{
		if(src.do_get_container() == this->do_get_container())
		{
			return this->do_get_pos() < src.do_get_pos();
		}
		return this->do_get_container() < src.do_get_container();
	}

	const ValueType &operator[](usize_t n)
	{
		if(n == 0)
			return **this;
		fastvec_const_iterator_t tmp = *this;
		tmp += n;
		return *tmp;
	}
};

template <class ValueType>
class fastvec_t :
	public fastvec_base_t
{
	usize_t alloc_levels;
	usize_t actual_size;
	
	// The first level has space allocated for 16 objects; 2nd level has space for 32; etc.
	typedef ref_t<raw_value_t<ValueType> > level_type;
	ref_t<level_type> r_levels;
	level_ref_t<ValueType> level;
	
	// note: 'index' is the offset within the level.
	void destroy_object(usize_t level_num, usize_t index)
	{
		const usize_t object_size_qwords = (sizeof(ValueType) + sizeof(U8) - 1) / sizeof(U8);
		U8 *level_data = level[level_num]->data;
		ValueType *object = (ValueType *)(level_data + object_size_qwords * index);
		object->~ValueType();		// call destructor
	}
	
public:
	typedef fastvec_iterator_t<ValueType> iterator;
	typedef fastvec_const_iterator_t<ValueType> const_iterator;
	
	iterator begin()
	{
		return fastvec_iterator_t<ValueType>(level, &actual_size, 0);
	}
	
	iterator end()
	{
		return fastvec_iterator_t<ValueType>(level, &actual_size);
	}
	
	const_iterator begin() const
	{
		return fastvec_const_iterator_t<ValueType>(level, &actual_size, 0);
	}
	
	const_iterator end() const
	{
		return fastvec_const_iterator_t<ValueType>(level, &actual_size);
	}

	fastvec_t() :
		alloc_levels(0),
		actual_size(0),
		level(&r_levels)
	{
	}

	fastvec_t(const fastvec_t &src) :
		alloc_levels(0),
		actual_size(0),
		level(&r_levels)
	{
		operator=(src);
	}

	fastvec_t &operator=(const fastvec_t &src)
	{
		if(&src == this)
			return *this;		// nothing to do !
		clear();
		if(src.empty())
			return *this;
		resize(src.size());
		iterator dest = begin();
		for(const_iterator i = src.begin(); i != src.end(); ++i, ++dest)
		{
			*dest = *i;
		}
		return *this;
	}
	
	template<class IteratorType>
	void append(IteratorType b, IteratorType e)
	{
		for(; b != e; ++b)
			push_back(*b);
	}
	
	// This constructor requires the iterators it's given, to support iterator subtraction (b - e).
	// See also append(), which does not have that requirement.
	template<class IteratorType>
	fastvec_t(IteratorType b, IteratorType e) :
		alloc_levels(0),
		actual_size(0),
		level(&r_levels)
	{
		if(b != e)
		{
			resize(e - b);

			iterator dest = begin();
			for(; b != e; ++b, ++dest)
				*dest = *b;
		}
	}
	
	~fastvec_t()
	{
		clear();
	}
	
	usize_t size() const
	{
		return actual_size;
	}
	
	bool empty() const
	{
		return size() == 0;
	}
	
	void clear()
	{
		if(empty() || alloc_levels == 0)
			return;
		
		for(usize_t i = 0; i < alloc_levels; ++i)
		{
			if(actual_size == 0 || level[i].is_null())
				break;
			
			usize_t pos_begin = pos_from_level(i);
			usize_t pos_end = pos_begin + get_level_size(i);
			if(pos_end > actual_size)
				pos_end = actual_size;
			usize_t level_size = pos_end - pos_begin;
				
			for(usize_t j = 0; j < level_size; ++j)
				destroy_object(i, j);	// hopefully there won't be any exceptions from this
				
			level[i].clear();
		}
		
		// Let's actually reclaim the space used to store level references, too, when clear() is called.
		level.clear();

		actual_size = 0;
		alloc_levels = 0;
	}

private:
	ValueType &get(usize_t pos)
	{
		usize_t level_num = 0, offset = 0;
		if(pos != 0)
		{
			level_num = level_from_pos(pos);
			offset = pos - pos_from_level(level_num);
		}

		U8 *level_data = level[level_num]->data;
		const usize_t object_size_qwords = (sizeof(ValueType) + sizeof(U8) - 1) / sizeof(U8);
		ValueType *object = (ValueType *)(level_data + object_size_qwords * offset);
		
		return *object;
	}
	
	const ValueType &cget(usize_t pos) const
	{
		usize_t level_num = 0, offset = 0;
		if(pos != 0)
		{
			level_num = level_from_pos(pos);
			offset = pos - pos_from_level(level_num);
		}

		U8 *level_data = level[level_num]->data;
		const usize_t object_size_qwords = (sizeof(ValueType) + sizeof(U8) - 1) / sizeof(U8);
		const ValueType *object = (ValueType *)(level_data + object_size_qwords * offset);
		
		return *object;
	}

	// pre: requested_size != 0 && requested_size < actual_size
	void shrink_to(usize_t requested_size)
	{
		// First, let's call destructors. Hopefully none of them will throw any exceptions.
		const usize_t object_size_qwords = (sizeof(ValueType) + sizeof(U8) - 1) / sizeof(U8);

		usize_t level_num = level_from_pos(requested_size);
		usize_t offset = requested_size - pos_from_level(level_num);
		U8 *level_data = level[level_num]->data;
		usize_t level_size = get_level_size(level_num);
		
		for(usize_t n = requested_size; n < actual_size; ++n)
		{
			if(offset == level_size)
			{
				++level_num;
				offset = 0;
				level_data = level[level_num]->data;
				level_size = get_level_size(level_num);
			}
		
			usize_t offset_end = actual_size - n;
			if(offset_end > level_size)
				offset_end = level_size;
			
			ValueType *object = (ValueType *)(level_data + object_size_qwords * offset);
			object->~ValueType();		// call destructor. Hope for no exceptions!
			
			++offset;
		}
		
		actual_size = requested_size;
		
		// Note that a precondition on entry is: requested_size != 0.
		usize_t levels_required = 1 + level_from_pos(requested_size - 1);

		// Free unneeded levels. We hope for no exceptions here, too.
		while(alloc_levels > levels_required)
		{
			//>>std::cout << "Deallocating level " << alloc_levels - 1 << "." << std::endl;
			level[alloc_levels - 1].clear();
			--alloc_levels;
		}
	}
	
	// pre: requested_size != 0 && requested_size > actual_size
	void grow_to(usize_t requested_size, ValueType &src)
	{
		usize_t max_level = level_from_pos(requested_size - 1);
		
		usize_t current_level = level_from_pos(actual_size);
		
		while(alloc_levels <= max_level)
		{
			//>>std::cout << "Allocating level: " << alloc_levels << std::endl;
			level.set(alloc_levels, ref_t<raw_value_t<ValueType> >::allocate_array(get_level_size(alloc_levels)));
			
			++alloc_levels;
		}
		
		usize_t current_pos = actual_size - pos_from_level(current_level);
		usize_t level_size = get_level_size(current_level);
		
		const usize_t object_size_qwords = (sizeof(ValueType) + sizeof(U8) - 1) / sizeof(U8);
		
		U8 *level_data = level[current_level]->data;

		while(actual_size < requested_size)
		{
			if(current_pos == level_size)
			{
				current_pos = 0;
				++current_level;
				level_size = get_level_size(current_level);
				level_data = level[current_level]->data;
			}

			// Call copy constructor.
			ValueType *object = (ValueType *)(level_data + object_size_qwords * current_pos);
			(void) new (object) ValueType(src);		// placement new, calls copy constructor
			
			++actual_size;
			++current_pos;
		}
	}

	void do_resize(usize_t requested_size, ValueType &src)
	{
		if(actual_size == requested_size)
			return;		// nothing to do

		if(requested_size == 0)
		{
			clear();
			return;
		}

		if(requested_size > actual_size)
		{
			grow_to(requested_size, src);
		}
		else
		{
			shrink_to(requested_size);
		}
	}

public:
	template <class VT>
	void resize(usize_t requested_size, VT src)
	{
		do_resize(requested_size, src);
	}

	void resize(usize_t requested_size)
	{
		ValueType tmp;
		do_resize(requested_size, tmp);
	}

	template <class VT>
	void push_back(VT src)
	{
		resize(actual_size + 1, src);
	}
	
	ValueType &front()
	{
		return get(0);
	}
	
	const ValueType &front() const
	{
		return cget(0);
	}
	
	ValueType &back()
	{
		return get(actual_size - 1);
	}
	
	const ValueType &back() const
	{
		return cget(actual_size - 1);
	}
	
	void pop_back()
	{
		if(empty())
			return;
		resize(actual_size - 1);
	}
	
	const ValueType &operator[](usize_t n) const
	{
		return cget(n);
	}
	
	ValueType &operator[](usize_t n)
	{
		return get(n);
	}
};

}	// namespace fastvec_internal

using fastvec_internal::fastvec_t;

}	// namespace infrared_sysbase

#endif	// l_fastvec_h__infrared_isb__included
